//给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。 
//
// 注意，根节点 root 位于深度 1 。 
//
// 加法规则如下: 
//
// 
// 给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。 
// cur 原来的左子树应该是新的左子树根的左子树。 
// cur 原来的右子树应该是新的右子树根的右子树。 
// 如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。 
// 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入: root = [4,2,6,3,1,5], val = 1, depth = 2
//输出: [4,1,1,2,null,null,6,3,1,5] 
//
// 示例 2: 
//
// 
//
// 
//输入: root = [4,2,null,3,1], val = 1, depth = 3
//输出:  [4,2,null,1,1,3,null,null,1]
// 
//
// 
//
// 提示: 
//
// 
// 节点数在 [1, 10⁴] 范围内 
// 树的深度在 [1, 10⁴]范围内 
// -100 <= Node.val <= 100 
// -10⁵ <= val <= 10⁵ 
// 1 <= depth <= the depth of tree + 1 
// 
//
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 144 👎 0

package leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class _623_AddOneRowToTree {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        Solution solution = new _623_AddOneRowToTree().new Solution();
        TreeNode root = new TreeNode(4, new TreeNode(2, new TreeNode(3), new TreeNode(1)), new TreeNode(6, new TreeNode(5), null));
        int val = 1;
        int depth = 2;
        TreeNode res = solution.addOneRow(root, val, depth);
        System.out.println();
    }

    class Solution {
        public TreeNode addOneRow(TreeNode root, int val, int depth) {
            if (depth == 1) {
                return new TreeNode(val, root, null);
            }
            List<TreeNode> curLevel = new ArrayList<TreeNode>();
            curLevel.add(root);
            for (int i = 1; i < depth - 1; i++) {
                List<TreeNode> tmpt = new ArrayList<TreeNode>();
                for (TreeNode node : curLevel) {
                    if (node.left != null) {
                        tmpt.add(node.left);
                    }
                    if (node.right != null) {
                        tmpt.add(node.right);
                    }
                }
                curLevel = tmpt;
            }
            for (TreeNode node : curLevel) {
                node.left = new TreeNode(val, node.left, null);
                node.right = new TreeNode(val, null, node.right);
            }
            return root;
        }
    }


    class Solution2 {
        public TreeNode addOneRow(TreeNode root, int val, int depth) {
            if (root == null) {
                return null;
            }
            if (depth == 1) {
                return new TreeNode(val, root, null);
            }
            if (depth == 2) {
                root.left = new TreeNode(val, root.left, null);
                root.right = new TreeNode(val, null, root.right);
            } else {
                root.left = addOneRow(root.left, val, depth - 1);
                root.right = addOneRow(root.right, val, depth - 1);
            }
            return root;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution1 {
        public TreeNode addOneRow(TreeNode root, int val, int depth) {
            if (depth == 1) {
                TreeNode res = new TreeNode(val, root, null);
                return res;
            } else {
                Deque<TreeNode> queue = new ArrayDeque<>();
                int deep = 1;
                queue.addLast(root);
                final int MAX = 100001;
                TreeNode NULL = new TreeNode(MAX);
                queue.addLast(NULL);
                TreeNode cur;
                Deque<TreeNode> pre = new ArrayDeque<>();
                Deque<TreeNode> now = new ArrayDeque<>();
                while (!queue.isEmpty()) {
                    cur = queue.removeFirst();
                    if (cur.val == MAX) {
                        if (queue.isEmpty()) {
                            break;
                        }
                        deep++;
                        queue.addLast(NULL);
                        continue;
                    }

                    if (deep == depth - 1) {
                        pre.addLast(cur);
                    }

                    System.out.println(cur.val + " " + deep);
                    if (cur.left != null) {
                        queue.addLast(cur.left);
                    }
                    if (cur.right != null) {
                        queue.addLast(cur.right);
                    }
                }
                while (!pre.isEmpty()) {
                    cur = pre.removeFirst();
                    cur.left = new TreeNode(val, cur.left, null);
                    cur.right = new TreeNode(val, null, cur.right);
                }
                return root;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}